#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

const int kMaxN = 8;

struct vertex {
  vector<pair<int, long long>> edges_;
} graph[kMaxN];

unordered_set<long long> status[1 << kMaxN];
int log_table[1 << kMaxN];
long long ans;

void DFS(int state, int n, long long r, long long k) {
  if (state + 1 == (1 << n)) {
    ans = min(r, ans);
    return;
  }
  if (status[state].count(r)) {
    return;
  }
  status[state].insert(r);
  for (int x = state; x; x ^= x & -x) {
    int u = log_table[x & (-x)];

    for (const pair<int, long long> &edge : graph[u].edges_) {
      if ((1 << edge.first) & state) {
        continue;
      }
      DFS(state | (1 << edge.first), n, (r + edge.second) % k, k);
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int n, m;
  long long k;

  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int u, v;
    long long w;

    cin >> u >> v >> w;
    u--, v--;
    graph[u].edges_.emplace_back(v, w);
    graph[v].edges_.emplace_back(u, w);
  }
  ans = k;
  for (int i = 0; i < n; i++) {
    log_table[1 << i] = i;
  }
  DFS(1, n, 0, k);
  cout << ans << endl;
  return 0;
}